/*****************************************************************************
 *   Copyright 2011 ZHUANG Yuan              	                             *
 *   SudokuITS as Final Year Project for BScCS, City University of Hong Kong *
 *                                      									 *
 *   Licensed under the Apache License, Version 2.0 (the "License");         *
 *   you may not use this file except in compliance with the License.        *
 *   You may obtain a copy of the License at                                 *
 *                                                                           *
 *   http://www.apache.org/licenses/LICENSE-2.0                              *
 *                                                                           *
 *   Unless required by applicable law or agreed to in writing, software     *
 *   distributed under the License is distributed on an "AS IS" BASIS,       *
 *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.*
 *   See the License for the specific language governing permissions and     *
 *   limitations under the License.                                          *
 *****************************************************************************/

package android.sudoku.its.expert;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

import android.sudoku.its.util.GameVariables;

public class StrategiesUtil {
	public List<Integer> mergeCandidateInHouse(List<List<Integer>> cm, int houseType, int houseIndex) {
		List<Integer> mergedCMHouse = new ArrayList<Integer>();
		final int DETERMINED_CELL = -1; 
		
		switch(houseType) {
			case GameVariables.ROW:				
				for (int col = 0; col < GameVariables.HOUSE_SIZE; col ++) {
					List<Integer> candidateOfACell = cm.get(houseIndex * GameVariables.HOUSE_SIZE + col);
					if (candidateOfACell.get(0) != DETERMINED_CELL)
						mergedCMHouse.addAll(candidateOfACell);									
				}
				break;
			case GameVariables.COLUMN:
				for (int row = 0; row < GameVariables.HOUSE_SIZE; row ++) {
					List<Integer> candidateOfACell = cm.get(row * GameVariables.HOUSE_SIZE + houseIndex);
					if (candidateOfACell.get(0) != DETERMINED_CELL)
						mergedCMHouse.addAll(candidateOfACell);	
				}
				break;
			case GameVariables.BLOCK:
				// Get the left top coordinate of a block
				int blockStartRow = (houseIndex/GameVariables.BLOCK_SIDE_LENGTH)*GameVariables.BLOCK_SIDE_LENGTH;
				int blockStartCol = (houseIndex%GameVariables.BLOCK_SIDE_LENGTH)*GameVariables.BLOCK_SIDE_LENGTH;
				for (int row=blockStartRow; row<(blockStartRow + GameVariables.BLOCK_SIDE_LENGTH); row++) 
					for (int col=blockStartCol; col<(blockStartCol + GameVariables.BLOCK_SIDE_LENGTH); col++) {
						List<Integer> candidateOfACell = cm.get(row * GameVariables.HOUSE_SIZE + col);
						if (candidateOfACell.get(0) != DETERMINED_CELL)
							mergedCMHouse.addAll(candidateOfACell);	
					}
				break;
		}
		return mergedCMHouse;
	}
	
	public List<Integer> findCandidateByFrequency(List<Integer> mergedCMHouse, int frequency) {
		List<Integer> possibleCandidates = new ArrayList<Integer>();		
		for (int i = 0; i < GameVariables.HOUSE_SIZE; i ++) {
			int count = Collections.frequency(mergedCMHouse, i);
			if (count == frequency) 
				possibleCandidates.add(i);
		}		
		return possibleCandidates;
	}
	
	public List<List<Integer>> getCandidatePosition(List<List<Integer>> cm, List<Integer> possibleCandidates, int houseType, int houseIndex) {
		// Create a list of list to store the positions of possible hidden pairs. 
		// Each sub-list contains two elements representing the two cells that the hidden pair is in
		List<List<Integer>> allPossibleCandidatesPositions = new ArrayList<List<Integer>>();
		int possibleCandidatesSize = possibleCandidates.size(); 
		for (int i = 0; i < possibleCandidatesSize; i ++) {
			int candidate = possibleCandidates.get(i);
			List<Integer> candidatePositions = new ArrayList<Integer>();
			
			switch (houseType) {
				case GameVariables.ROW:
					for (int col = 0; col < GameVariables.HOUSE_SIZE; col ++) {							
						List<Integer> candidateOfACell = cm.get(houseIndex * GameVariables.HOUSE_SIZE + col);
						if (candidateOfACell.contains(candidate))
							candidatePositions.add(col);							
					}
					break;
				case GameVariables.COLUMN:
					for (int row = 0; row < GameVariables.HOUSE_SIZE; row ++) {							
						List<Integer> candidateOfACell = cm.get(row * GameVariables.HOUSE_SIZE + houseIndex);
						if (candidateOfACell.contains(candidate))
							candidatePositions.add(row);							
					}
					break;
				case GameVariables.BLOCK:
					// Get the left top coordinate of a block
					int blockStartRow = (houseIndex/3)*3;
					int blockStartCol = (houseIndex%3)*3;
					for (int row=blockStartRow; row<(blockStartRow + GameVariables.BLOCK_SIDE_LENGTH); row++) 
						for (int col=blockStartCol; col<(blockStartCol + GameVariables.BLOCK_SIDE_LENGTH); col++) {
							List<Integer> candidateOfACell = cm.get(row * GameVariables.HOUSE_SIZE + col);
							if (candidateOfACell.contains(candidate))
								candidatePositions.add(row * GameVariables.HOUSE_SIZE + col);	
						}
					
					break;
			}
			
			allPossibleCandidatesPositions.add(candidatePositions);
		}
		
		return allPossibleCandidatesPositions;
	}
	
	protected List<List<Integer>> updateASM(List<List<Integer>> asm, int cellIndex, int strategyIndex) {		
		List<Integer> applicableStrategyForOneCell = asm.get(cellIndex);		
		if (!applicableStrategyForOneCell.contains(strategyIndex)) {
			applicableStrategyForOneCell.add(strategyIndex);
			asm.remove(cellIndex);
			asm.add(cellIndex, applicableStrategyForOneCell);
		}		
		return asm;
	}
	
	protected List<List<Integer>> updateASMForHiddenPairFunc(List<List<Integer>> asm, List<List<Integer>> allPossibleCandidatesPositions, List<Integer> candidatePositions, int houseType, int houseIndex) {
		int strategyIndex = GameVariables.HIDDEN_PAIR_INDEX;								
		for (int j = 0; j < 2; j ++) {
			int cellIndex = 0;
			switch(houseType) {
				case GameVariables.ROW:
					cellIndex = houseIndex * GameVariables.HOUSE_SIZE + candidatePositions.get(j); 
					break;
				case GameVariables.COLUMN:
					cellIndex = candidatePositions.get(j) * GameVariables.HOUSE_SIZE + houseIndex; 
					break;
				case GameVariables.BLOCK:
					cellIndex = candidatePositions.get(j);
					break;
			}
			asm = updateASM(asm, cellIndex, strategyIndex);
		}
		return asm;
	}
		
	public boolean ifHiddenPairApplicableFunc(List<List<Integer>> allPossibleCandidatesPositions, List<Integer> candidatePositions) {		
		boolean ifHiddenPairApplicable = false;
		int count = Collections.frequency(allPossibleCandidatesPositions, candidatePositions);
		if (count == 2) { // if two of the candidates share the same position
			return ifHiddenPairApplicable = true;
		}						
			
		return ifHiddenPairApplicable;
	}
	
	protected List<List<Integer>> updateASMForHiddenPairByHouse(List<List<Integer>> cm, List<List<Integer>> asm, int houseType) {
		for (int house = 0; house < GameVariables.HOUSE_SIZE; house ++) {
			/* Create a list that contains all candidates of this house */
			List<Integer> mergedCMHouse = mergeCandidateInHouse(cm, houseType, house);
			
			// It is only possible for a house to have more than 4 candidates to apply the Hidden Pair strategy
			if (mergedCMHouse.size() > 4) {								
				/* Find the candidate that appears exactly twice in this house */
				List<Integer> possibleCandidates = findCandidateByFrequency(mergedCMHouse, 2);

				/* Get the cell position of the occurrence of possible pairs */
				int possibleCandidatesSize = possibleCandidates.size(); 
				if (possibleCandidatesSize >= 2) { // if there are at least two candidates that appears exactly twice in this house				
					List<List<Integer>> allPossibleCandidatesPositions = getCandidatePosition(cm, possibleCandidates, houseType, house);					
					/* Compare the positions and find if there are any two of the candidates share the same positions */
					for (int i = 0; i < allPossibleCandidatesPositions.size(); i ++) {
						List<Integer> candidatePositions = allPossibleCandidatesPositions.get(i);
						if (ifHiddenPairApplicableFunc(allPossibleCandidatesPositions, candidatePositions))
							asm = updateASMForHiddenPairFunc(asm, allPossibleCandidatesPositions, candidatePositions, houseType, house);	
					}						
				}
			}
		}
		
		return asm;
	}

	protected int ifCandidateOccursCertainTimes(List<Integer> allCandidatesInHouse, List<Integer> candidateOfTargetCell, int frequency) {
		int resultCandidate = 0; // meaning that there's no such candidate that occurs n times, where n = frequency
	    
		Iterator<Integer> iterator = candidateOfTargetCell.iterator();
		for (int i = 0; i < candidateOfTargetCell.size(); i++) {	    		
	    	int candidate = iterator.next().intValue();
			if (Collections.frequency(allCandidatesInHouse, candidate) == frequency)
				return resultCandidate = candidate; // return the candidate that occurs n times, where n = frequency
	    }
	    
		return resultCandidate;
	}
	
	public int isHiddenSingleApplicableFunc(List<List<Integer>> cm, List<Integer> candidateOfTargetCell, int houseType, int houseIndex) {
		// Merge the candidates for all cells in this row into one list
		List<Integer> allCandidatesInHouse = mergeCandidateInHouse(cm, houseType, houseIndex);
		
		// Check if there is one candidate of the target cell that only occurs once in this row	
		return ifCandidateOccursCertainTimes(allCandidatesInHouse, candidateOfTargetCell, 1);
	}
}
